Principe
Méthode de dichotomie, méthode de bijection : algorithme de recherche d'un zéro d'une fonction qui consiste à répéter des partages d'un intervalle en deux parties puis à sélectionner un sous-intervalle dans lequel existe le zéro de la fonction
Méthode de la dichotomie :
On construit trois suites récurrentes :- \(a_0=a\), \(b_0=b\)
- \(\forall n\geqslant0,x_n=\frac{a_n+b_n}{2}\)
- $$\begin{array}{ll}g (x_n)=0&\implies&a_{n+1}=a_n\quad\text{ et }\quad b_{n+1}=b_n\\ g(a_n)g(b_n)\lt 0&\implies&a_{n+1}=a_n\quad\text{ et }\quad b_{n+1}=x_n\\ g(a_n)g(b_n)\gt 0&\implies&a_{n+1}=x_n\quad\text{ et }\quad b_{n+1}=b_n\end{array}$$,bn+1?\(
Alors \)(x_n)_n\( converge vers un zéro de \)g\(
Le principe de la dichotomie repose sur un corollaire du théorème des valeurs intermédiaires
(
Théorème des valeurs intermédiaires)
Calcul de l'erreur
Si l'on souhaite obtenir une valeur de \)c\( à \)10^{-N}\( près par principe de dichotomie, il faut que... \)$n\geqslant\frac{N+\log(b-a)}{\log2}$$
(
Logarithme en base a)
Exemple
Exemple de raisonnement par dichotomie : démonstration du
Théorème des valeurs intermédiaires
